#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

int res = -1;
int hash1[10000] = {0};

int edges[1000][1000];
int N, M;
int ti[1000] = {0};

struct Node
{
    int dis = 1e6;
    int id;
};

struct mycompare
{
    bool operator()(Node A, Node B)
    {
        return A.dis > B.dis;
    }
};


void dij()
{
    priority_queue<Node, vector<Node>, mycompare> Q;

    Node st;
    st.dis = 0, st.id = 1;
    hash1[st.id] = 1;
    Q.push(st);

    while(!Q.empty())
    {
        Node now = Q.top();
        Q.pop();
        if(now.id == N)
        {
            res = now.dis;
            break;
        }

        for(int i = 1; i <= N; i++)
        {
            if(!hash1[i] && i!=now.id && edges[now.id][i] > 0)
            {
                Node temp;
                temp.id = i;
                if(temp.dis > now.dis + edges[now.id][temp.id])
                    temp.dis = now.dis + edges[now.id][temp.id];
                Q.push(temp);
            }
        }
    }

}

int main()
{
    cin >> N >> M;

    memset(edges, -1, sizeof(edges));

    for(int i = 1; i <= N; i++)
    {
        cin >> ti[i];
    }

    for(int i = 1; i <= M; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        if(edges[u][v] > w + ti[v] || edges[u][v] == -1)
        {
            edges[u][v] = w + ti[v];
            if(v == N)edges[u][v] -= ti[v];
        }
        
        if(edges[v][u] > w + ti[u] || edges[v][u] == -1)
        {
        edges[v][u] = w + ti[u];
        if(u == N)edges[v][u] -= ti[u];
        }
    }

    dij();
    cout << res;

    return 0;
}
